#include <bits/stdc++.h>
using namespace std;
#define S(a, b) memset(a, b, sizeof(a))
const int maxn = 5e3+10, INF = 0x3f3f3f3f;

int  dp[maxn][maxn], add[maxn][maxn], sa[maxn], ea[maxn], sb[maxn], eb[maxn];
char a[maxn], b[maxn]; int la, lb;

void update(int i, int j, int op){
    if(op == 0){
        dp[i+1][j] = min(dp[i+1][j], dp[i][j] + add[i][j]);
        add[i+1][j] = add[i][j];

        char c = a[i+1];
        if(sa[c] == ea[c] && sb[c] == INF) return;
        if(i+1==sa[c] && j<sb[c]) add[i+1][j]++;
        else if(i+1==ea[c] && (!eb[c] || j>=eb[c])) add[i+1][j]--;
    }else{
        dp[i][j+1] = min(dp[i][j+1], dp[i][j] + add[i][j]);
        add[i][j+1] = add[i][j];

        char c = b[j+1];
        if(sb[c] == eb[c] && sa[c] == INF) return;
        if(j+1==sb[c] &&  i<sa[c]) add[i][j+1]++;
        else if(j+1==eb[c] && (!ea[c] || i>=ea[c])) add[i][j+1]--;
    }
    
}

void finish(int i, int j){
    while(i<la){
        update(i, j, 0);
        ++i;
    }
    while(j<lb){
        update(i, j, 1);
        ++j;
    }
}

int main() {
//    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
    int T; cin >> T;
    while(T--){
        S(dp, INF), S(sa, INF), S(sb, INF), S(ea, 0), S(eb, 0);//, S(add, 0);
        scanf("%s%s", a+1, b+1);
//        cin >> a >> b;
        la = strlen(a+1), lb = strlen(b+1);

        for (int i=1; i<=la; ++i) {
            char c = a[i];
            if(sa[c] == INF) sa[c] = i;
            ea[c] = i;
        }
        for (int i=1; i<=lb; ++i) {
            char c = b[i];
            if(sb[c] == INF) sb[c] = i;
            eb[c] = i;
        }

        dp[0][0] = 0;
        add[0][0] = 0;
        for (int i = 0; i <= la; ++i) {
            for (int j = 0; j <= lb; ++j) {
                if(!i && !j) continue;

                int v1 = INF, v2 = INF;
                if(i) v1 = dp[i-1][j] + add[i-1][j];
                if(j) v2 = dp[i][j-1] + add[i][j-1];
                dp[i][j] = min(v1, v2);

                if(i) {
                    add[i][j] = add[i-1][j];
                    if(sa[a[i]] == i && sb[a[i]] > j) add[i][j]++;
                    if(ea[a[i]] == i && eb[a[i]] <= j) add[i][j]--;
                } else if(j) {
                    add[i][j] = add[i][j - 1];
                    if(sb[b[j]] == j && sa[b[j]] > i) add[i][j]++;
                    if(eb[b[j]] == j && ea[b[j]] <= i) add[i][j]--;
                }
            }
        }
        printf("%d\n", dp[la][lb]);
//        cout << dp[la][lb] << endl;
    }
    return 0;
}